import java.util.*;

public class Solution332 {

    int flag=0;

    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String,Integer> first=new HashMap<>();
        int[] next=new int[tickets.size()];
        String[] go=new String[tickets.size()];
        int count=0;
        for (List<String> ticket : tickets) {
            first.putIfAbsent(ticket.get(0),-1);
            next[count]=first.get(ticket.get(0));
            first.put(ticket.get(0),count);
            go[count]=ticket.get(1);
            count++;
        }
        int[] visit=new int[tickets.size()];
        List<String> ans=new ArrayList<>();
        dfs(0,"JFK",first,next,go,visit,ans);
        ans.add(0,"JFK");
        return ans;
    }

    private void dfs(int k, String current, Map<String, Integer> first, int[] next, String[] go, int[] visit, List<String> ans) {
        if (k==visit.length){
            flag=1;
            return;
        }
        List<Pair> list=new ArrayList<>();
        int p=first.getOrDefault(current,-1);
        while (p!=-1){
            if (visit[p]==0) {
                list.add(new Pair(go[p],p));
            }
            p=next[p];
        }
        list.sort(Comparator.comparing(a -> a.name));
        for (Pair pair : list) {
            ans.add(pair.name);
            visit[pair.id]=1;
            dfs(k+1,pair.name,first,next,go,visit,ans);
            if (flag==1){
                return;
            }
            ans.remove(ans.size()-1);
            visit[pair.id]=0;
        }
    }

    static class Pair{
        String name;
        int id;

        public Pair(String name, int id) {
            this.name = name;
            this.id = id;
        }
    }

    public static void main(String[] args) {
        List<List<String>> lists=new ArrayList<>();
        List<String> l1=new ArrayList<>();
        l1.add("JFK");l1.add("SFO");lists.add(l1);
        List<String> l2=new ArrayList<>();
        l2.add("JFK");l2.add("ATL");lists.add(l2);
        List<String> l3=new ArrayList<>();
        l3.add("SFO");l3.add("ATL");lists.add(l3);
        List<String> l4=new ArrayList<>();
        l4.add("ATL");l4.add("JFK");lists.add(l4);
        List<String> l5=new ArrayList<>();
        l5.add("ATL");l5.add("SFO");lists.add(l5);
        System.out.println(new Solution332().findItinerary(lists));
    }
}
